class Solution {
    int dx[8] = { 1, -1, 0, 0, 1, -1, 1, -1 };
    int dy[8] = { 1, -1, 1, -1, 0, 0, -1, 1};
    int getLiveCnt(int i, int j, int m, int n, vector<vector<int>>& board)
    {
        int live = 0;
        for(int k = 0; k < 8; k++)
        {
            int x = i + dx[k], y = j + dy[k];
            if(x >= 0 && x < m && y >= 0 && y < n)
            {
                if((board[x][y] & 1) == 1)
                    live++;
            }
        }
        return live;
    }
public:
    void gameOfLife(vector<vector<int>>& board) {
        // 位运算
        // 死 -> 死     0 -> 00
        // 死 -> 活     0 -> 10
        // 活 -> 死     1 -> 01
        // 活 -> 活     1 -> 11
        int m = board.size(), n = board[0].size();

        for(int i = 0; i < m; i++)
        {
            for(int j = 0; j < n; j++)
            {
                int cur = board[i][j];
                int live = getLiveCnt(i, j, m, n, board);
                if(cur == 1)
                {
                    if(live == 2 || live == 3)
                    {
                        // 活 -> 活
                        board[i][j] |= (1 << 1);
                    }
                    else
                    {}
                }
                else
                {
                    if(live == 3)
                    {
                        // 死 -> 活
                        board[i][j] |= (1 << 1);
                    }
                    else
                    {}
                }
            }
        }

        // 更新为bit位倒数第二位的值
        for(int i = 0; i < m; i++)
        {
            for(int j = 0; j < n; j++)
            {
                if(board[i][j] & (1 << 1))
                    board[i][j] = 1;
                else
                    board[i][j] = 0;
            }
        }


        // 下面这种办法比较挫，时空复杂度是O(m * n)
        // vector<vector<int>> tmp(board);
        // int m = board.size(), n = board[0].size();
        // int dx[] = { 1, -1, 0, 0, 1, -1, 1, -1 };
        // int dy[] = { 1, -1, 1, -1, 0, 0, -1, 1};

        // for(int i = 0; i < m; i++)
        // {
        //     for(int j = 0; j < n; j++)
        //     {
        //         int live = 0, dead = 0;
        //         for(int k = 0; k < 8; k++)
        //         {
        //             int x = i + dx[k], y = j + dy[k];
        //             if(x >= 0 && x < m && y >= 0 && y < n)
        //             {
        //                 if(tmp[x][y] == 1)
        //                     live++;
        //                 else
        //                     dead++;
        //             }
        //         }

        //         if(board[i][j] == 1)
        //         {
        //             if(live < 2 || live > 3)
        //                 board[i][j] = 0;
        //         }
        //         else
        //         {
        //             if(live == 3)
        //                 board[i][j] = 1;
        //         }
        //     }
        // }
    }
};